#include <stdio.h>
#include <limits.h>
#include "loser_tree.h"


#define K 5
#define MIN_KEY -1
#define MAX_KEY INT_MAX

struct ex_node {
	int nr;
	int top;
	int e[20];
};

struct ex_node ex[K+1] = {
	{.nr = 3, .top = 0, .e = {6, 15, 25, MAX_KEY}},
	{.nr = 3, .top = 0, .e = {12, 37, 48, MAX_KEY}},
	{.nr = 3, .top = 0, .e = {10, 15, 16, MAX_KEY}},
	{.nr = 3, .top = 0, .e = {8, 9, 20, MAX_KEY}},
	{.nr = 3, .top = 0, .e = {20, 22, 40, MAX_KEY}},
	{.nr = 3, .top = 0, .e = {MIN_KEY, MIN_KEY, MIN_KEY}}
};

#define dump_ls(ls, b) do {(void)ls; (void)b;} while(0)
#define dump_b(b)

void _dump_ls(int ls[], struct ex_node b[])
{
	int i, j, n = 1;
	int t, top, v;

	printf(" -- ls -- \n");
	j = 0;
	for (i = 0; i < 4; i++) {
		while (j < n) {
			t = ls[j];
			if (t < 0) {
				v = -2;
			} else if (t >= K) {
				v = -3;
			} else {
				top = b[t].top;
				v = b[t].e[top];
			}
			printf("[[%d]=%d]=%d  ",
				j, ls[j], v);
			j++;
		}
		printf("\n");
		n = n * 2;
	}
}

void _dump_b(struct ex_node b[])
{
	int i, j;

	for (i = 0; i <= K; i++) {
		printf("b[%d] = {.nr = %d, .top = %d, .e = { ",
			i, b[i].nr, b[i].top);
		for(j = b[i].top; j < b[i].nr; j++) {
			printf("%d, ", b[i].e[j]);
		}
		printf("}}\n");
	}
}
int get_key(struct ex_node *b, int i)
{
	return b[i].e[b[i].top];
}

void adjust(int ls[], struct ex_node b[], int s)
{
	int t, tmp, k1, k2;

	t = (s + K) / 2;
	while (t > 0) {
		k1 = get_key(b, s);
		k2 = get_key(b, ls[t]);
		printf("key[%d]=%d, key[ls[%d]=%d]=%d\n",
			s, k1, t, ls[t], k2);
		if (k1 > k2) {
			printf("  swap\n");
			tmp = s;
			s = ls[t];
			ls[t] = tmp;
		}

		t = t/2;
	}
	ls[0] = s;
}


void create(int ls[], struct ex_node b[])
{
	int i;

	b[K].e[b[K].top] = MIN_KEY;

	for (i = 0; i < K; i++)
		ls[i] = K;

	for (i = K-1; i >= 0; i--) {
		dump_ls(ls, b);
		dump_b(b);
		printf("create adj(%d)\n", i);
		adjust(ls, b, i);
	}
}



void k_merge(int ls[], struct ex_node b[])
{
	int q;

	create(ls, b);

	while(get_key(b, ls[0]) != MAX_KEY) {
		q = ls[0];
		printf("\n == q=%d, v=%d ==\n", q, get_key(b, q));
		dump_ls(ls, b);
		dump_b(b);
		b[q].top++;
		adjust(ls, b, q);
	}
}

static int min_key=MIN_KEY;
static int max_key=MAX_KEY;

long lt_cmp_key(void *k1, void *k2)
{
	return *(int *)k1 - *(int *)k2;
}

void lt_get_key(int idx, void **key)
{
	int top;

	if (idx < 0) {
		*(int **)key = &max_key;
		return;
	}

	if (idx >= K) {
		*(int **)key = &min_key;
		return;
	}

	top = ex[idx].top;
	*(int **)key = &ex[idx].e[top];
}

int main()
{
	struct loser_tree *lt;
	int q;
	int *kp;
	int key;
	int *ls;

	lt = lt_create(K, 16, (getkey_t)lt_get_key, lt_cmp_key);

	ls = lt_get_ls(lt);

	while (1) {
		lt_top(lt, &q);
		dump_ls(ls, ex);
		lt_get_key(q, (void **)&kp);
		key = *kp;
		fprintf(stderr, " q=%d, key=%d\n", q, key);
		if (key == MAX_KEY)
			break;
		ex[q].top++;
		lt_adjust(lt, q);
	}

	lt_destroy(lt);
	return 0;
}



